'''
https://leetcode.cn/problems/burst-balloons/description/
'''
from functools import cache
from typing import List


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # l左边没爆，r右边没爆
        @cache
        def f(i, j):
            if i == j:
                return nums[i - 1] * nums[i] * nums[j + 1]
            # x a b c d e x
            res = 0
            for m in range(i, j + 1):
                res = max(res, f(i, m - 1) + f(m + 1, j) + nums[i - 1] * nums[m] * nums[j + 1])
            return res
        n = len(nums)
        nums = [1] + nums + [1]
        return f(1, n)

    # dp 打表
    def maxCoins2(self, nums: List[int]) -> int:
        n = len(nums)
        nums = [1] + nums + [1]
        dp = [[0] * (n+2) for _ in range(n+2)]
        # 第一维度依赖后边的，第二维度依赖前边的
        # i <= j 只用关心上三角
        # 普遍位置依赖下边行当前列， 当前行左边的，从下往上，从左往右
        # 初始位置 i == j, dp[i][i] = nums[i - 1] * nums[i] * nums[j + 1]
        for i in range(1, n+1):
            dp[i][i] = nums[i - 1] * nums[i] * nums[i + 1]
        for i in range(n-1, -1, -1):
            for j in range(i+1, n + 1):
                res = 0
                for m in range(i, j + 1):
                    res = max(res, dp[i][m - 1] + dp[m + 1][j] + nums[i - 1] * nums[m] * nums[j + 1])
                dp[i][j] = res
        # print(*dp, sep='\n')
        return dp[1][n]

nums = [3,1,5,8]
print(Solution().maxCoins2(nums))